\documentclass[10pt,twoside,twocolumn]{IEEEtran}

%\documentclass[12pt,peerreview]{IEEEtran}

\usepackage{times}
\usepackage{pst-all}
\usepackage[dvips]{graphicx}
\graphicspath{{./}{fig/}}
\usepackage{url}
\usepackage{rotating}

\def\MAT#1{{\boldsymbol{#1}} } % need amsbsy
\usepackage{amsbsy}
\newcommand{\mc}{\multicolumn}
\def\btimes{\odot}
\def\Obj{\emph}

\begin{document}
\title{Spare Capacity Allocation in Two-Layer Networks}

% DRCN headers
%\author{\authorblockN{Yu Liu\authorrefmark{2},
%David Tipper\authorrefmark{3},  
%Korn Vajanapoom\authorrefmark{3}}
%\authorblockA{\authorrefmark{2}OPNET Technologies, Inc.\\
%200 Regency Forest Drive, Cary, North Carolina 27511, USA\\ email: yliu@opnet.com}
%\authorblockA{\authorrefmark{3}Department of Information Science and Telecommunications\\
%University of Pittsburgh, Pittsburgh, Pennsylvania 15260, USA\\
%email: tipper@tele.pitt.edu, kov2@pitt.edu}}

%Following are for IEEE Journals
\author{Yu~Liu,~\IEEEmembership{Member,~IEEE,} 
David~Tipper,~\IEEEmembership{Senior~Member,~IEEE,}
Korn~Vajanapoom~
\thanks{Y. Liu is with OPNET Technologies, 
5201 Great America Parkway, Suite 529,
Santa Clara, CA 95054, USA (email: yliu@opnet.com).}%
\thanks{D. Tipper and K.~Vajanapoom are with the
Telecommunications Program, 
University of Pittsburgh, Pittsburgh, PA 15260 USA (email: tipper@tele.pitt.edu, kov2@pitt.edu).}
\thanks{This work was supported by the National Science Foundation
under Grant ANIR 9980516 and by the Defense Advanced Research Projects
Agency under Grant F30602-97-1-0257.  An earlier version of this paper was presented at
the 5th Design of Reliable Communication Networks (DRCN) workshop, Island of Ischia, Italy, 2005.}
}

%\markboth{{Revision for J-SAC Special Issue on Multi-Layer Traffic Engineering}} %Revision \today}
%{Spare Capacity Allocation in Two-Layer Networks}
%\markboth{submitted for DRCN 2005, \today}
%{Liu, et. al.: Spare Capacity Allocation in Multi-Layer Networks}

% \pubid has to be in front of \maketitle
%\pubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
% must use following command in the second column
%\pubidadjcol

%\IEEEaftertitletext{\vspace{-1\baselineskip}}


\maketitle

%\IEEEpeerreviewmaketitle

\begin{abstract}
In this paper we consider the problem of provisioning spare capacity in two-layer
backbone networks using shared backup path protection. 
First, two spare capacity allocation (SCA) optimization problems are
formulated as  integer linear programming (ILP) models for the
cases of protection at the top layer against failures at the bottom
layer.  
The first model captures failure propagation using overlay information
between two layers for backup paths to meet diversity requirements.
The second model improves bandwidth efficiency by moving  spare
capacity sharing from the top layer to the bottom layer.  This exposes
a tradeoff between bandwidth efficiency and extra cross-layer
operation. 
Next, the SCA model for common pool protection is developed to allow
spare capacity sharing between two layers. 
Our previous SCA heuristic technique, successive survivable routing (SSR)
is extended for these optimization problems.   
Numerical results 
for a variety of networks indicate that the common pool protection is attractive to
enhance bandwidth efficiency without loss of survivability and that the SSR heuristic quickly results in near optimal solutions. 
\end{abstract}

\begin{keywords}
multi-layer network design, 
traffic engineering,
spare capacity allocation,
resilient network design,
shared risk link group.
\end{keywords}

\section{Introduction}
%\PARstart{S}urvivability 
Survivability in the face of failures has become an essential property of backbone transport networks.
Current backbone data networks have multiple layers such as IP/MPLS over SONET over an optical layer
% It might converge towards a GMPLS controlled multi-layer architecture in the near future.
and are converging toward a  two-layer architecture of IP/MPLS or GMPLS over an optical transport layer. 

Survivability techniques in two-layer networks can be classified as: survivability at the bottom layer, survivability at the top layer, and survivability at both layers, depending on, the layer in which the survivability technique is deployed \cite{vasseur:survive}. In the bottom-layer  approach, recovery from a failure is performed only at the bottom layer (e.g., recovering failed lightpaths in an optical transport network).  This scheme has the benefits that it is simple and provides fast recovery of aggregate traffic. However, the major drawback of this scheme is that it cannot recover from failures that occur at the top layer, such as, the failure of a top-layer router or its interfaces.  In the survivability at the top-layer scheme, failure recovery is performed only at the top layer, (e.g., recovering failed label switched paths (LSPs) in a MPLS network using fast reroute).  The advantage of this scheme is that it can recover from failures that occur in both layers. It also allows a service differentiation among top-layer flows by recovering each individual flow at the top layer, which is difficult in the bottom-layer survivability scheme where an aggregate of top-layer flows is recovered. Among the drawbacks of this approach are its complexity and slower speed of  fault recovery.  

 One of the major problems in the survivability of such two-layer networks is  \emph{failure propagation}, which occurs when the failure of a bottom-layer link or node results in the simultaneous failure of  multiple top-layer links \cite{vasseur:survive,grover:survive,pioro:survive}.  If failure propagation is not considered appropriately in multi-layer networks, the survivability at the top layer technique may fail to recover the communication services after a failure. 
Several approaches have been proposed to design survivable virtual 
topologies at the top layer while taking  failure propagation into
account~\cite{corchat00:ton, modiano01:survtopo, kurant:survrout,
ducatelle:global04, giroire:infocom03, xu:netmag04}.  
In part due to failure propagation, each layer of a network will
typically employ self-healing capabilities to address faults occurring
in their own layer. In such a multi-layer scheme, coordination between
layers is required to provide an efficient recovery process upon a
failure.  This coordination is called an escalation strategy, which
determines which layer will perform a recovery first in response to a
particular failure, and when and how a responsibility will be
transferred to another layer if the current layer fails to recover
from the failure \cite{vasseur:survive,Demeester:commag99}. 

Recently several papers have appeared on protection in IP/MPLS over WDM  networks~\cite{Sahasrabuddhe:jsac02,Zheng:comnet06,Koo:icc03,Ou:jsac03}. 
%
In \cite{Sahasrabuddhe:jsac02}, the authors provide two classes of integer linear programming (ILP) models for IP restoration and WDM shared protection.  These models consider the equipment constraints on transmitters and receivers and compare restoration requirements at both layers. Heuristic algorithms are used to compare the maximum guaranteed network capacity and recovery time.  
%
Zheng and Mohan \cite{Zheng:comnet06} evaluate  protection schemes at the LSP level and the lightpath level for  dynamic traffic in IP/MPLS over WDM networks. Their results indicate that  inter-level sharing (ILS) could improve the resource utilization. 
%
Koo, et. al., \cite{Koo:icc03} study the ILP model to minimize the total cost to route primary and backup LSPs over lightpaths using MPLS protection against the failures of a Label Switched Router (LSR) and Shared Risk Link Groups (SRLG)s.  A two-phase heuristic to find primary and backup LSPs sequentially is proposed.
%
Ou, et. al., \cite{Ou:jsac03} describe three traffic grooming schemes on IP/WDM networks: Protection-At-Lightpath, Separated Protection-At-Connection, and Mixed Protection-At-Connection. Shared backup protection on lightpaths or links against single fiber failures are assumed.  Heuristic routing algorithms are developed to compare the bandwidth blocking ratios and the resource efficiency ratios under various loads. 


In this paper, we provide several ILP models for the 
SCA problem in two-layer networks.  We consider not only  failure
propagation between layers but also \emph{cross layer spare capacity sharing}.  
Initially we focus on the fault independent shared backup path restoration. 
%The main focus of our study is on the SCA models for restoration in
%the top layer.  
First, we consider the SCA problem for the case when fault recovery is performed at the bottom layer only. Next we derive two models for the SCA problem when  fault recovery occurs only in the top-layer network. 
The first model captures failure propagation by extending the
matrix-based SCA formulation for a single layer network given in~\cite{liu:ton05}.
The second model further improves the first one by allowing the
top-layer survivability technique to share spare capacity at the bottom layer.
Next, the SCA model for  protection at both layers with 
spare capacity sharing across layers is presented. 
This model will have working and backup routes on both layers. 
In addition, we show how failure dependent shared backup path restoration with and without stub release can be incorporated into the SCA models.
Numerical results for a variety of network scenarios
%show that the proposed models can be solved by
are given for each SCA model. The numerical results are determined using
both the commercial optimization solver CPLEX and a heuristic algorithm, called the successive survivable routing (SSR) algorithm. 
Lastly, these results are discussed and the conclusions are presented.

% pulls up column for \pubid
%%%  \pubidadjcol

\section{Spare Capacity Allocation Modeling}
\label{sec:models}
%%% This section is a brief review of SCA and SSR, with the notation
The survivable two-layer network design problem contains a survivable topology layout problem 
and the SCA problem. This paper formulates them separately.
The main reason is because of their different design cycles. 
The network topology has a much longer design cycle of multiple years.
On the other hand, backbone LSP connections have shorter life spans ranging from weeks to months. 
The partitioning of these two problems allows one to trade off  design optimality with a better solution speed for the survivable network design problem.
In the appendix, the survivable topology layout problem is formulated. 
This problem finds a valid inter-layer mapping so that any single bottom-layer failure 
will not partition the top-layer topology.  
%This is one of the prerequisite conditions to successfully provision 
 %backup paths in the top-layer SCA problem. 
This section briefly reviews the SCA model and the SSR algorithm for a single layer network presented in ~\cite{liu:ton05}, in order to provide background for the two-layer SCA models and SSR extensions in the next section. %%% This section is a brief review of SCA and SSR, with the notation


\subsection{The Single Layer Spare Capacity Allocation Model}
We assume the network under study uses failure independent path restoration (FID) for an arbitrary failure condition.  FID is also called  path restoration with disjoint routes, where a backup path is always disjoint (either link or node) from its working path.  
We assume all traffic flows require a 100\% restoration level 
for any failure, which requires that all
affected flows be detoured to their backup paths upon any given
failure.  Provisioning enough spare capacity is the prerequisite condition to such restoration.  
The acronyms used in this paper are given in Table~\ref{tbl:acronym}.
Similarly, the notation adopted is summarized in Table~\ref{tbl:notation}.
\begin{table}[!htbp]
\begin{center}
\caption{Acronyms}
\label{tbl:acronym}
\begin{tabular}{@{\hspace{1mm}}r@{\hspace{2mm}}p{0.38\textwidth}@{\hspace{1mm}}}
                                %0.28\textwidth}} %for two column
\hline \hline
SCA & Spare capacity allocation\\
SPM & Spare provision matrix\\
SSR & Successive survivable routing algorithm\\
%SR  & Survivable routing\\
%RAFT& Resource aggregation for fault tolerance~\cite{Dovrolis:ACMCCR98}\\
%SPI & Sharing with Partial Information~\cite{kodialam00:survrouting}\\
BB  & Branch and bound algorithm\\
%LP  & Linear programming relaxation\\
InP & Integer programming\\
%NS  & No-Sharing scheme~\cite{kodialam00:survrouting}\\
%FMT & Fault Management Table~\cite{Dovrolis:ACMCCR98}\\
FID & Failure-independent path restoration\\
FD  & Failure-dependent path restoration\\
FDStubR & Failure-dependent path restoration with stub release\\
iff & if and only if \\
\hline \hline
\end{tabular}
\end{center}
\end{table}


\begin{table}[!phtb]
\begin{center}
\caption{Notation}
\label{tbl:notation}
\begin{tabular}{@{\hspace{1mm}}c@{\hspace{2mm}}p{
      %0.8\textwidth}@{\hspace{1mm}}} %for one column
      0.28\textwidth}}                %for two column
\hline \hline
$N, L, R, K$ & Numbers of nodes, links, flows and failures\\
$n, l, r, k$ & Indices of nodes, links, flows and failures\\
% $1\leq n \leq N, 1\leq l \leq L, 1\leq r \leq R, 1\leq k \leq K$\\
%$r$ & Index of flows\\
$\MAT{P}=\{\MAT{p}_{r}\}=\{p_{rl}\}$ & Working path link incidence matrix\\
$\MAT{Q}=\{\MAT{q}_{r}\}=\{q_{rl}\}$ & Backup path link incidence matrix\\
%$m_r$ & Traffic demand of flow $r$, $r \in {\mathcal{D}}$\\
%$\MAT{m}=\{m_r\}$ & Vector of traffic demand of flow $r$,
%$r \in {\mathcal{D}}$\\
$\MAT{M}=\mbox{Diag}(\{m_r\})$ & Diagonal matrix of bandwidth 
$m_r$ of flow $r$\\
$\MAT{G}=\{g_{lk}\}_{L\times K}$ & Spare provision matrix,
     $g_{lk}$ is spare capacity on link $l$ for failure $k$\\
$\MAT{G}^r=\{g^r_{lk}\}_{L\times K}$ & Contribution of flow $r$ to
$\MAT{G}$\\
%$s_i$ & Integer variable denoting spare capacity needed on link~$i$\\
$\MAT{s}=\{s_l\}_{L\times 1}$ & Spare capacity vector\\
$\MAT{\phi}=\{\phi_l\}_{L\times 1}$ & Spare capacity cost function \\
%$\MAT{h}^w=\{h^w_r\}$ & Vector of working path lengths\\
%$\MAT{h}^b=\{h^b_r\}$ & Vector of backup path lengths\\
$W, S$ & Total working, spare capacity\\
$\eta=S/W$ & Network redundancy\\
$o(r),d(r)$ & Origin/destination nodes of flow $r$\\
$\MAT{v}_r=\{v_{rl}\}$ & Vector of  incremental spare capacity cost for flow $r$ on link $l$ \\
$\MAT{B}=\{b_{nl}\}_{N\times L}$ & Node link incidence matrix \\
$\MAT{D}=\{d_{rn}\}_{R\times N}$ &  Flow node incidence matrix \\
%$\MAT{D}^o$, $\MAT{D}^d$&  Binary incidence matrixes between flow and
%source node, or destination node, $\MAT{D}^o-\MAT{D}^d=\MAT{D}$ \\
$\MAT{F}=\{f_{kl}\}_{K\times L}$ & Failure link incidence
matrix, $f_{kl}=1$ iff link $l$ fails in failure scenario $k$ \\
$\MAT{U}=\{u_{rk}\}_{R\times K}$ &  Flow failure incidence
matrix, $u_{rk}=1$ iff failure scenario $k$ will affect flow~$r$'s working path\\
$\MAT{T}=\{t_{rl}\}_{R\times L}$ &  Flow tabu-link matrix,
$t_{rl}=1$ iff link $l$ should not be used on flow $r$'s backup path\\
\hline \hline
\end{tabular}
\end{center}
\end{table}

We model an uncapacitated network 
\footnote{
The assumption of unlimited link bandwidth allows this study to concentrate on 
the efficiency of spare capacity sharing with little influence from link capacity.  
The results could be useful for lightly loaded networks.  
The realistic constraints such as link capacity constraints or traffic delay constraints can be added for network planning purposes. 
}
by a directed graph of $N$ nodes, $L$ links, and $R$ flows. 
Flow $r, 1\leq r\leq R$ has its
origin/destination node pair $(o(r), d(r))$ and traffic demand $m_{r}$.
Working and backup paths of flow $r$ are represented by two $1\times L$ 
binary row vectors $\MAT{p}_{r}=\{p_{rl}\}$ and
$\MAT{q}_{r}=\{q_{rl}\}$ respectively.   
The $l$-th element in one of the vectors
equals to one \emph{if and only if} (iff) the corresponding path uses link~$l$. 
The path link incidence matrices for working and backup paths 
are the collections of these vectors, forming two 
$R\times L$ matrices $\MAT{P}=\{p_{rl}\}$ and $\MAT{Q}=\{q_{rl}\}$ 
respectively.
Let $\MAT{M}=\mbox{Diag}(\{m_r\}_{R\times 1})$ denote the diagonal 
matrix representing demand bandwidth.
The topology is represented by the node-link incidence matrix
$\MAT{B}=(b_{nl})_{N\times L}$ where $b_{nl} = 1$ \emph{or} $-1$ iff
 node~$n$ is the origin \emph{or} the destination node of link~$l$.   
$\MAT{D}=(d_{rn})_{R\times N}$ 
is the flow node incidence matrix where $d_{rn}=1$ or $-1$ 
iff $o(r) = n$ or $d(r) = n$.  
We characterize  $K$ failure scenarios in a binary matrix
$\MAT{F}=\{\MAT{f}_{k}\}_{K\times 1}=\{f_{kl}\}_{K\times L}$. 
%
The row vector $\MAT{f}_k$ in
$\MAT{F}$ is for failure scenario $k$ and its element $f_{kl}$
equals one iff link $l$ fails in scenario $k$.
In this way, each failure scenario includes a set of one or more
links that will fail simultaneously in the scenario.
For a failed node, all its
adjacent links are marked as failed.   
We also denote a flow failure incidence matrix
$\MAT{U}=\{\MAT{u}_{r}\}_{R\times 1}=\{u_{rk}\}_{R\times K}$,
where $u_{rk}=1$ iff flow $r$ will be affected by failure $k$, and 
$u_{rk}=0$ otherwise.
The flow tabu-link matrix $\MAT{T}=\{\MAT{t}_{r}\}_{R\times 1} =
\{t_{rl}\}_{R\times L}$  has  
$t_{rl}=1$  iff the backup path of flow $r$ should not use link $l$,
and $t_{rl}=0$ otherwise.  
We can find $\MAT{U}$ and $\MAT{T}$ given $\MAT{P}$ and $\MAT{F}$ as
shown in equations (\ref{eq:flowf}) and~(\ref{eq:tabuT}) respectively.
A binary matrix multiplication operation ``$\btimes$'' is used in 
equations (\ref{eq:flowf}) and (\ref{eq:tabuT}). 
It is a matrix multiply operator that is identical to normal matrix multiplication except that the general numerical addition $1+1=2$ will be replaced 
by the boolean addition
$1+1=1$ as described in~\cite{kolman96:disc_math}.  
Using this binary operator, the logical relations
among links, paths and failure scenarios are simplified into 
two matrix operations.  

Let $\MAT{G}=\{g_{lk}\}_{L\times K}$  denote the 
\emph{spare provision matrix} (SPM) whose elements $g_{lk}$ are the minimum
spare capacity required on link $l$ when failure~$k$ occurs.  Note that
$K=L$ when the SCA protects all single link failures.
Given the backup paths~$\MAT{Q}$, the demand bandwidth matrix 
$\MAT{M}$, the working path $\MAT{P}$, and the failure matrix $\MAT{F}$,
$G$ can be determined by equation~(\ref{eq:spmcomp2}) 
with the help of~(\ref{eq:flowf}). 
The minimum spare capacity required on each link is denoted by the
column vector $\MAT{s} = \{s_l\}_{L\times 1}$, which is found 
in equation (\ref{eq:pickmax2}). 
The function $\max$ in~(\ref{eq:pickmax2}) asserts that an element in
$\MAT{s}$ is equal to the 
maximum element in the corresponding row of $\MAT{G}$.  
%
It is equivalent to $\MAT{s} \geq \MAT{G}$ in this optimization model.
%This is a linear programming format.
%The operator $\geq$
%between a column vector $\MAT{s}$ and a matrix $\MAT{G}$ guarantees that
%any element in $\MAT{s}$ is always not less than any 
%elements in the corresponding row of $\MAT{G}$.  
%
Let $\phi_l$ denote the cost function of spare capacity on link $l$.  
$\MAT{\phi} = \{ \phi_l\}_{L\times 1}$ is a column vector of these
cost functions and $\MAT{\phi}(\MAT{s})$
gives the cost vector of 
the spare capacities on all links.
The total cost of spare capacity in the network is 
$\MAT{e}^T \MAT{\phi}(\MAT{s})$, 
where $\MAT{e}$ is unit column vector of size $L$.  
Here for simplicity, we assume all cost functions $\MAT{\phi}(\MAT{s})$ are
identity functions, i.e., $\MAT{\phi}(\MAT{s}) = \MAT{s} $.

Given the notation and definitions above the spare capacity allocation (SCA) problem can be formulated as follows. 
\begin{eqnarray}
  \displaystyle \min_{\MAT{Q},\MAT{s}} 
  & S = \MAT{e}^T \MAT{s}
  \label{eq:MinCost2}  \\
  \mbox{s.t.} 
  & \MAT{s} = \max \MAT{G}
  \label{eq:pickmax2}   \\
  & \MAT{G} = \MAT{Q}^T \MAT{M} \MAT{U}
  \label{eq:spmcomp2}  \\
  & \MAT{T} + \MAT{Q} \leq 1
  \label{eq:CompDisjoint} \\
  & \MAT{Q} \MAT{B}^T = \MAT{D}
  \label{eq:feasiblePath2}  \\
  & \MAT{Q}: binary 
  \label{eq:integrity2}
\end{eqnarray}
\begin{eqnarray}
  & \MAT{U} = \MAT{P} \btimes \MAT{F}^T
  \label{eq:flowf}  \\
  & \MAT{T} =\MAT{U}\btimes \MAT{F}
  \label{eq:tabuT} 
\end{eqnarray}

This SCA problem has the objective to
minimize the total spare capacity in~(\ref{eq:MinCost2}) with the
constraints~(\ref{eq:pickmax2})--(\ref{eq:tabuT}).  The decision variables are the backup path matrix $\MAT{Q}$ and the spare capacity vector $\MAT{s}$. 
Constraints~(\ref{eq:pickmax2}) and~(\ref{eq:spmcomp2})
associates these variables, 
i.e., the spare capacity allocation $\MAT{s}$ is derived from 
the backup paths in $\MAT{Q}$.  
%Note that constraint~(\ref{eq:spmcomp2}) can be replaced
% by~(\ref{eqn:Cr2}) and~(\ref{eqn:Cr2C2}).  
%
Constraint~(\ref{eq:CompDisjoint}) guarantees that every backup path will
not use any link which might fail simultaneously with any link on its working
path.  
%For any single link failure, 
%it assures that backup paths are link-disjointed from their working paths.
Flow conservation constraint~(\ref{eq:feasiblePath2}) guarantees that
backup paths given in $\MAT{Q}$ are feasible paths of flows in a
directed network.  
Note, the incidence matrices $\MAT{U}$ and
$\MAT{T}$ are precomputed.  The matrix $\MAT{U}$ indicates the failure cases
that will influence the working paths.  The matrix $\MAT{T}$ indicates the links that should be
avoided in the backup paths. 
In this paper, the link load, the traffic flows and their routes are assumed symmetric.  
In a directed network, each link might have two directions with asymmetric load.  In this case, the dimensions of these matrices should be doubled, i.e. $2L$, instead of $L$. 
More detailed explanation of the above SCA model is 
in~\cite[eq.(7)-(14)]{liu:ton05}.

\subsection{The Successive Survivable Routing Algorithm}

The SCA model formulated above is a mixed ILP  problem.  It is NP-complete. Hence, solving the problem for large networks is infeasible using standard integer programming solution methods. 
In \cite{liu:ton05}, we proposed the successive survivable routing (SSR) heuristic algorithm.  
The SSR algorithm 
finds solutions
by routing backup paths iteratively.  
Each backup path computation uses the shortest path algorithm. 
The link routing metric is the \emph{incremental spare capacity} $\MAT{v}_r=\{v_{rl}\}$. 
It is computed from the most recent spare provision matrix 
that is further based on previously routed backup paths. 
After all flows find their backup paths, 
SSR continues to update existing backup paths whenever a new one
could use less spare capacity. 
This process keeps reducing total spare capacity until it converges, 
(i.e., no more backup path updates).
Different random ordering of the flows for routing backup paths  are used to provide diversity and avoid local minima.  
The best solution is used as the final one, which in numerical results given in ~\cite{liu:ton05} show as near optimal. The SSR  scheme includes five steps for flow $r$ as shown below.  
\begin{itemize}
\item Step 1 calculates the failure impact vector $\MAT{u}_r$ and the tabu link vector $\MAT{t}_r$ using the failure matrix $\MAT{F}$, the working path row vector $\MAT{p}_r$, and the destination node $d(r)$.  $\MAT{u}_r$ and $\MAT{t}_r$ are the $r$-th row vectors in the matrices $\MAT{U}$ and $\MAT{T}$ found in~(\ref{eq:flowf}) and~(\ref{eq:tabuT}). 
\item Step 2 recomputes the spare provision matrix $\MAT{G}$ using~(\ref{eq:spmcomp2}) periodically, i.e., before each backup route update.
\item Step 3 calculates the link metric $\MAT{v}_r$ from $\MAT{G}$ and  traffic flow $r$'s contribution $\MAT{G}^r = m_r (\MAT{q}_r^T  \MAT{u}_r), 1 \leq r \leq R$ as follows:
\newline
(a) Given $\MAT{G}$, $\MAT{q}_r$ and $\MAT{G}^r$ for current
flow $r$,  
let $\MAT{G}^{-r} = \MAT{G}-\MAT{G}^r$ and 
$\MAT{s}^{-r}= \max \MAT{G}^{-r}$ be the spare provision matrix
and the link spare capacity vector after current backup path $\MAT{q}_r$ is
removed.  
\newline
(b) Let $\MAT{q}_r^{*}$ denote an alternative backup path for flow $r$, 
and function $\MAT{G}^{r*}(\MAT{q}_r^{*})=m_r {\MAT{q}_r^{*}}^T  \MAT{u}_r$.  
Then, this new path $\MAT{q}_r^{*}$ produces a new spare capacity
reservation vector in a function format of $\MAT{s}^{*}(\MAT{q}_r^{*})=
\max(\MAT{G}^{-r} + \MAT{G}^{r*}(\MAT{q}_r^{*}))$.
\newline
(c) Let $\MAT{q}_r^{*}=\MAT{e}-\MAT{t}_r$, which assumes the backup
path uses all non-tabu links. Then, we can find the vector of 
\emph{link metrics} for flow $r$ as 
\begin{eqnarray}  \MAT{v}_r &=& \{v_{rl}\}_{L\times 1} 
  \nonumber\\
  &=& \MAT{\phi}(\MAT{s}^{*}(\MAT{e}-\MAT{t}_r))-\MAT{\phi}(\MAT{s}^{-r}),
                \label{eq:incr_spare}
\end{eqnarray}
where $\MAT{t}_r$ is the binary flow tabu-link vector of flow $r$. 
The element $v_{rl}$ is the cost of the incremental spare
capacity on link $l$ if this link is used on the backup path.

\item Step 4 uses the shortest path algorithm with the link metric $\MAT{v}_r$ to find a new or updated backup path $\MAT{q}_r^{new}$.  This path excludes all the tabu links indicated in $\MAT{t}_r$. 
\item Step 5 replaces the original backup path $\MAT{q}_r$ with the new backup path $\MAT{q}_r^{new}$ if the new one has the lower cost based on the link metrics in $\MAT{v}_r$, i.e., only when $\MAT{v}_r^T \MAT{q}_r > \MAT{v}_r^T \MAT{q}_r^{new}$. 
\item After Step 5, SSR continues to Step~2 to update the backup path for another flow.  This iterative process not only finds backup route, but also helps to minimize the required total spare capacity shared among all backup routes.  
\item After all flows have found backup paths, the iteration continues until the termination condition is met.  The termination condition can be: (1) there is no backup update for all flows in the recent iteration, or (2) when the maximum number of updates is reached.  
\end{itemize}
More detailed description of SSR is in~\cite[\S V]{liu:ton05}.

\section{Two-Layer SCA Models}
\label{sec:sca} 
In this section, we extend the previous SCA model to a two-layer network. 
In the top-layer network case, 
the  notation of the previous section
is reused, 
and the same notation with the superscript ``$b$'' is 
used for the bottom layer.  
A top-layer link is carried by a bottom-layer path. 
Overlay information is defined by 
the interlayer link incidence matrix
$\MAT{H}=\{h_{ij}\}_{L\times L^b}$,
where $1\leq i\leq L$, $1\leq j\leq L^b$.  
Element $h_{ij}$ 
equals to one \emph{iff} the top-layer link $i$ uses
the bottom-layer link $j$.  
Given the top-layer spare capacity allocation vector $\MAT{s}$,
its equivalent bottom-layer spare capacity vector $\MAT{s}^b$ is given by:
\begin{equation}
  \label{eq:pathcvt}
  \MAT{s}^b = \MAT{H}^T \MAT{s}.
\end{equation}

Usually, each bottom-layer link carries one or multiple top-layer links; therefore a failure of single bottom-layer link could tear down multiple top-layer links simultaneously. In order to provide  restoration at the top layer, the interlayer link incidence matrix $\MAT{H}$ should guarantee that a failure of any single bottom-layer link would not partition the top-layer topology. 
This property is called \emph{immunity from failure propagation}.  
A math programming model to find such a mapping $\MAT{H}$ for the single link failure case is
provided  in~\cite{modiano01:survtopo}.  
%It is called in~\cite[\S6.2]{liu:dissertation}, 
%where the matrix-based formulation is provided.
%The overlay information $\MAT{H}$ is used as the input to the following SCA models.
In the Appendix, we provide a matrix based formulation 
for this survivable topology layout problem.  
This model considers various failure scenarios in addition to single link failures. 
%The survivable topology layout problem is introduced in the Appendix.  
The solution of this model provides the inter-layer link mapping $\MAT{H}$
so that the top-layer topology has enough
connectivity to be resilient to  bottom-layer failures.  

Given the interlayer information $\MAT{H}$ 
several multi-layer SCA problems are formulated.  
First, the multi-layer SCA problem for the FID path restoration case is
discussed. 
In the FID case, each flow has a single backup path disjoint from 
any failures that affect its working path.  
Based on the layer where the FID restoration scheme exists, 
the SCA model can be classified into three approaches, namely: (1) restoration
at the bottom layer, (2) restoration at the top layer, or (3) restoration at both layers.  
Lastly, the SCA problems for 
the failure-dependent (FD) path restoration case  with and without stub release are
discussed. 


\subsection{Restoration at the bottom layer}
\label{sec:bottomonly}

%When the traffic flows are presented at the bottom layer, it is
%naturally to use the single layer SCA model in~\cite{liu:ton05} to
%provision the spare capacity.  

When the traffic flows are at the top layer, 
but the fault protection is only available at the bottom layer,  
each top-layer \emph{link} needs to have
a bottom-layer backup path preplanned besides its working path.
The top-layer traffic flow is not aware of the
bottom-layer restoration.  
This scheme is simple and it can deliver fast restoration upon failure.
However, it might not protect all top-layer failures such as 
the failure of a top-layer router or its interfaces.

The SCA model can be simplified to one at the bottom layer only.
Assuming the top-layer links are protected individually at the
bottom layer, 
the modifications to the SCA problem of the previous section are 
the bottom-layer working paths are 
derived from the layout information $\MAT{H}$
in~(\ref{eq:bottomlink}), and 
the traffic matrix $\MAT{M}^b$ is changed. Specifically, $\MAT{M}^b$  
is a $L \times L$ diagonal matrix with diagonal elements $m_r^b$ equal to 
the carried traffic $w_l$ on the top-layer links $l, 1\leq l \leq
L$ in~(\ref{equ:bottomflow}).   
\begin{equation}
  \label{eq:bottomlink}
  \MAT{P}^b = \MAT{H}
\end{equation}
\begin{equation}
  \label{equ:bottomflow}
  \MAT{M}^b = \emph{Diag}(m_r^b) = \mbox{Diag}(w_l, 1\leq l \leq L).
\end{equation}
Thus we solve the single layer SCA model of the previous section with modifications of (\ref{eq:bottomlink}) and (\ref{equ:bottomflow}).
%In the numerical study section, instead of using the demand mapping above, 
%the bottom layer has a separate set of full mesh unit flows.
%Each traffic demand uses the shortest hop route, that has at least one
%failure-disjoint backup path, as its working path.
%The backup paths are found using either SSR or BB as in~\cite{liu:ton05}.   

\subsection{Restoration at the top layer}
\label{sec:MinU}

When the restoration is at the top layer, equations 
(\ref{eq:MinCost2})-(\ref{eq:tabuT}) in the previous section 
are extended based on two alternate usages of the overlay information
$\MAT{H}$. We denote the two models proposed as [A] and [B] and modifications are denoted by 
superscripts added to variables in the models. 


\subsubsection*{\textbf{Model A}: 
Use of overlay information for failure propagation}
\label{sec:MinU2}
To protect against failure propagation 
of any single bottom-layer link failures, 
the overlay information $\MAT{H}$ is used to derive 
the failure scenario matrix $\MAT{F}$ for the top-layer SCA model 
as shown in~(\ref{eq:higherlink}). 
The flow failure incidence matrix $\MAT{U}$ 
and the spare provision matrix
$\MAT{G}^{[A]}$ are modified in~(\ref{eq:flowf1}) and~(\ref{eq:spmcomp1}) to
replace~(\ref{eq:flowf}) and $\MAT{G}$ in~(\ref{eq:spmcomp2}) respectively.
%(7) and~(11) in~\cite{liu:ton05}. 
\begin{equation}
  \label{eq:higherlink}
  \MAT{F} =  \MAT{F}^b \btimes \MAT{H}^T
\end{equation}
\begin{equation}
  \label{eq:flowf1} 
  \MAT{U} = \MAT{P} \btimes {\MAT{F}}^T = \MAT{P} \btimes
  ({\MAT{F}}^b \btimes \MAT{H})^T = \MAT{P} \btimes
  \MAT{H} \btimes {\MAT{F}^b}^T 
\end{equation}
\begin{equation}
  \label{eq:spmcomp1}
  \MAT{G}^{[A]} = {\MAT{Q}}^T \MAT{M} \MAT{U} 
   = {\MAT{Q}}^T \MAT{M} (\MAT{P}\btimes \MAT{H} \btimes {\MAT{F}^b}^T)
\end{equation}

In addition, the objective function
to minimize the total spare capacity~(\ref{eq:MinCost2}) 
is replaced by~(\ref{eq:MinU2}),
where  $\MAT{e}^T \MAT{H}^T$ is used to 
compute the actual spare capacity at the bottom layer 
reserved by the top-layer links. 
\begin{eqnarray}
  \displaystyle \min_{\MAT{Q}} S^{[A]}
  & = &  \MAT{e}^T \MAT{s}^b = \MAT{e}^T \MAT{H}^T \MAT{s} 
  \label{eq:MinU2} 
\end{eqnarray}

%This SCA model encapsulate the failure propagation from the overlay matrix $\MAT{H}$.  

\subsubsection*{\textbf{Model B}: 
Use of overlay information for both failure propagation and 
cross-layer spare capacity reservation}
\label{sec:MinU3}

In addition to using the
overlay information for  failure propagation, 
the second model 
computes the top-layer spare capacity sharing at the bottom layer instead of at
the top layer.
Since every top-layer link traverses one or more bottom-layer links,
spare capacity sharing on these bottom-layer links could further minimize the total spare capacity required.
The disadvantage of this model is the requirement of a method for
the top layer to record and 
reserve spare capacity on the bottom-layer links.
%This  might require a  cross-layer reservation protocol in
%the control plane. 

\begin{figure}[!htb]
  \begin{center}
    \includegraphics{fig1}
    \caption{Network 0: 5-node overlay network}
    \label{fig:twolayertopo5}
  \end{center}
\end{figure}

As an example to illustrate this approach consider
the two-layer network of Fig.~\ref{fig:twolayertopo5}. 
The overlay information $\MAT{H}$ for the network is given in~(\ref{equ:net0H}).
In the figure,  
two working flows \Obj{a--b} and \Obj{c--d} at the top-layer 
traverse the bottom-layer links \Obj{1} and \Obj{5} respectively. 
Their backup paths are \Obj{a--c--b} and \Obj{c--b--a--d} respectively.  
%At the bottom layer, their spare capacity on link \Obj{3}
%(\Obj{b--c}) can be shared at the top layer.  Moreover, 
The backup paths use the top-layer links \Obj{2} (\Obj{a--c}) and \Obj{3}
(\Obj{a--d}) respectively.
The bottom-layer paths of these top-layer links 
 overlap on the bottom-layer
link \Obj{2} (\Obj{a--e}) whose spare capacity could 
be shared by the backup paths.
In this example, the top-layer not only uses the overlay information $\MAT{H}$ 
to avoid  failure propagation, but also shares spare
capacity  at the bottom layer  to achieve lower redundancy. 
\begin{equation}
  \label{equ:net0H}
  \MAT{H} = \left( 
    \begin{array}{ccccccc}
      1&0&0&0&0&0&0 \\
      0&1&0&0&0&1&0 \\
      0&1&0&0&0&0&1 \\
      0&0&1&0&0&0&0 \\
      0&0&1&0&1&0&0 \\
      0&0&0&0&1&0&0 \\
    \end{array} \right) 
\end{equation}

This spare capacity sharing scheme is equivalent to: 
(i) converting  all
backup paths in $\MAT{Q}$ at the top layer into ones at the bottom layer
by multiplexing them with $\MAT{H}$.  
%This is similar to the conversion of the column link spare capacity vector in~(\ref{eq:pathcvt}) except each backup path is a row vector in the backup path matrix $\MAT{Q}$.
(ii) finding the spare capacity reserved at the bottom layer 
\begin{equation}
  \displaystyle \MAT{s}^b = \max ( (\MAT{Q}\MAT{H})^T \MAT{M} \MAT{U}) 
 = \max(\MAT{H}^T \MAT{G}^{[A]}).
\label{eq:s_b}
\end{equation}
(iii) then minimizing the objective function, the total spare
capacity 
% in~(\ref{eq:MinU3}).  
\begin{equation}
  \displaystyle \min_{\MAT{Q}} S^{[B]}  
   = \MAT{e}^T \MAT{s}^b 
   =
   \MAT{e}^T \max(\MAT{H}^T \MAT{G}^{[A]}).
  \label{eq:MinU3} 
\end{equation}

Since $\max(\MAT{H}^T \MAT{G}^{[A]}) \le \MAT{H}^T \max
(\MAT{G}^{[A]})$, 
the total spare capacity using Model B will be  equal to or smaller
than that in Model~A.
\begin{equation}
  \label{eq:s3les2}
  S^{[B]} \le S^{[A]}
\end{equation}


\subsection{Modified Successive Survivable Routing Algorithm}
\label{sec:modified_ssr}
Model B requires  modifications of  the SSR algorithm~\cite[\S V]{liu:ton05} to approximately solve the optimization problem.  
In this model, spare capacity sharing has been moved from the top
layer 
down to the bottom layer. Thus the spare provision
matrix and the computation of the incremental spare capacity vector 
are both moved down to the bottom layer as well.  
Routing backup paths at the top layer needs to use the overlay
information matrix $\MAT{H}$ in the modified SSR algorithm  as follows.

%\begin{itemize}
%\item
In Step~1, 
%in order to compute the backup path for flow $r$ at the top layer, 
given the working path vector $\MAT{p}_r$ and the failure matrix $\MAT{F}$,  
the failure vector $\MAT{u}_r$ and the tabu-link
vector $\MAT{t}_r$ are computed.  
%This step remains the same.

%\item
In Step~2, the top-layer spare provision matrix $\MAT{G}^{[A]}$ is
updated periodically.
%\item
In the end of Step~2, as shown in Model~B,  
the spare provision matrix $\MAT{G}^{[A]}$ is converted to its
bottom-layer equivalent $\MAT{H}^T \MAT{G}^{[A]}$
in~(\ref{eq:s_b}).  

%\item 
In Step~3,
we assume symbol $\MAT{G}$ is equivalent to $\MAT{G}^{[A]}$ in
Model~B.  It contains four phases:

%\begin{enumerate}

%\item
(a)
First, we need to derive the spare provision matrix after the current
backup path $\MAT{q}_r$ is removed.
It is denoted by 
$\MAT{G}^{-r}$, 
and is found using the top-layer spare provision matrix $\MAT{G}$,
the flow $r$'s SPM contribution $\MAT{G}^r.$ Specifically, 
$\MAT{G}^{-r} = \MAT{G} - \MAT{G}^r.$
%\item
Next, based on~(\ref{eq:s_b}), 
the bottom-layer spare capacity $\MAT{s^b}^{-r}$ after
removing   the backup path of flow $r$ is determined as
\begin{equation} 
{\MAT{s}^b}^{-r}=\max (\MAT{H}^T \MAT{G}^{-r}).
\label{eq:s_b_minus_r}
\end{equation}

%\item
(b)
Let $\MAT{q}^*_r$ denote an alternative backup path for flow~$r$.
Let 
$\MAT{G}^{r*}(\MAT{q}^*_r) = m_r {\MAT{q}^*_r}^T \MAT{u}_r$ denote the
SPM contribution matrix based on this backup path. 
Then, the new spare capacity reservation vector based on this backup
path is denoted as 
\begin{equation}
{\MAT{s}^b}^* (\MAT{q}^*_r) = \max (\MAT{H}^T
 (\MAT{G}^{-r}+\MAT{G}^{r*}(\MAT{q}^*_r)).
\label{eq:s_b_star}
\end{equation}

%\item 
(c) 
Let $\MAT{q}^*_r = \MAT{e} - \MAT{t}_r$, which assumes the backup path
is using all non-tabu links.  Then, we can find the incremental spare
capacity vector for flow $r$ at the bottom layer as
\begin{eqnarray}
\MAT{v}^b_r & = & \{v^b_{rl}\}_{L^b \times 1}
 = \MAT{\phi}^b({\MAT{s}^b}^*(\MAT{e}-\MAT{t}_r)) -
                  \MAT{\phi}^b({\MAT{s}^b}^{-r})
\nonumber \\
            & = & {\MAT{s}^b}^*(\MAT{e}-\MAT{t}_r) -{\MAT{s}^b}^{-r},
\label{eq:bottom_v}
\end{eqnarray}
where $\MAT{t}_r$ is the binary flow tabu-link vector of flow $r$.
The element $v^b_{rl}$ is the incremental spare capacity cost on
link $l$ at the bottom layer if this link is used by a top-layer link
on the backup path.

%\item
(d)
At the end of Step~3,
the incremental spare capacity vector $\MAT{v}_r$ at the top layer 
is derived from its equivalent vector $\MAT{v}_r^{b}$ at the
bottom layer by 
\begin{equation}
  \label{eq:incr_spareTop}
  \MAT{v}_r =  \MAT{H} \MAT{v}^b_r .
\end{equation}

%\end{enumerate}

%\item
Step~4 and~5 remain the same as the original SSR algorithm.
Step~4 first excludes all the tabu links marked in $\MAT{t}_r$, then uses a shortest path algorithm with link metrics $\MAT{v}_r$ to find an updated backup path $\MAT{q}^{new}_r$ at the top layer.  
In Step~5, the original backup path $\MAT{q}_r$ is replaced by the new path $\MAT{q}^{new}_r$ when the new path has a lower cost based on the link metrics $\MAT{v}_r$:
\begin{equation}
\MAT{q}_r = \MAT{q}^{new}_r, \mbox{if } \MAT{v}_r^T \MAT{q}_r > \MAT{v}_r^T \MAT{q}^{new}_r.
\end{equation}
Then the spare provision matrix $\MAT{G}^{[A]}$ and the spare capacity vector $\MAT{s}$ are updated to reflect this change accordingly. 

After Step~5, SSR continues to Step~2 to compute or update the backup path of another flow.  This iteration process keeps improving the total cost of the spare capacity.  It stops when no backup path update in all flows improves the cost. 
Additional termination conditions after Step~5 use a maximum number of total backup updates or a maximum execution time to terminate the algorithm. 
% In the numerical studies presented here, the algorithm converges within tens of iterations.  The algorithm converges when the iteration do not update any backup routes.  In this study, the maximum iteration number is set at a large number of 100.
%\end{itemize}

Notice that the above steps are modified from the original ones 
to use the overlay information matrix $\MAT{H}$ to translate SPM information between layers.  
%The original flowchart in~\cite[Fig.~4]{liu:ton05} 
%remains unchanged. 



\subsection{Restoration at both layers}
\label{sec:bothlayer}

When both layers use  shared backup path protection,
sharing the  spare capacity across layers might
further reduce the  redundancy.
This concept is also called  \emph{common pool
survivability} in~\cite{Demeester:commag99}.  
%Here we provide the formulation based on the SCA Model~B.  
When both layers are resilient to the same
set of bottom-layer failure scenarios, 
the spare capacity on both layers can be shared if 
their spare provision matrices are exchanged.  
The top-layer spare provision matrix $\MAT{G}^{[A]}$, used in both
Model~A and~B, is transformed
and merged with the spare provision matrix $\MAT{G}^b$ at the bottom
layer 
\begin{equation}
  \label{eq:downmap}
  \MAT{G}^{[C]} = \MAT{G}^b + \MAT{H}^T \MAT{G}^{[A]} .
\end{equation}

The objective function for the SCA problem is modified as shown
in~(\ref{eq:MinSpareBoth}).  
Notice that this objective value $S^{[C]}$ is less
than the total spare capacity used when both layers have the shared path
protection individually, i.e. $S^b + S^{[B]}$.  
\begin{eqnarray}
  \displaystyle \min_{\MAT{Q},\MAT{Q}^b} S^{[C]}  
  & = &  \MAT{e}^T \max \MAT{G}^{[C]} 
   =  \MAT{e}^T \max (\MAT{G}^b + \MAT{H}^T \MAT{G}^{[A]}) 
\nonumber \\
  & \leq &  \MAT{e}^T \max \MAT{G}^b +\MAT{e}^T \max(\MAT{H}^T \MAT{G}^{[A]})
\nonumber \\
  & = &  S^b + S^{[B]}
  \label{eq:MinSpareBoth} 
\end{eqnarray}

In the SSR algorithm, both layers perform their single layer SSR algorithms
but using different link routing metrics.  
The top layer  uses $\MAT{H}$  in the
modified SSR algorithm in
\S\ref{sec:modified_ssr}.  
It needs an additional change in Step~3:
The $\max(x)$ operation to compute the spare capacity vector $\MAT{s}^b$ 
in~(\ref{eq:s_b_minus_r}) and~(\ref{eq:s_b_star})
should  include the bottom-layer SPM matrix
$\MAT{G}^b$, i.e. $\max(\MAT{G}^b +x)$. 
In this way, both layers share a common spare capacity provision
matrix $\MAT{G}^{[C]}$.  
In effect the layers  cooperate to further improve spare capacity sharing.   


\subsection{Failure-dependent path restoration at the top layer}
\label{sec:fd}

All of the models above assume FID path
restoration. 
The SCA problem for the failure-dependent (FD) path restoration has
been discussed in~\cite{iras98,Xiong:TON99}.  
It allows multiple backup routes to protect the same working route.
Each of these backup routes will protect one or more failure scenarios.
Previously in~\cite{liu:drcn01} and~\cite[Ch.~6]{liu:dissertation}, 
the FD path restoration has been modeled in a matrix format.
This section extends this matrix model for FD path
restoration to two-layer networks. 

%We use Model A where the overlay information $\MAT{H}$ 
%is used for the failure propagation.

The arbitrary
bottom-layer failures are captured in the failure matrix $\MAT{F}$
in~(\ref{eq:higherlink}).
In order to compute backup paths for any individual failures, 
equation~(\ref{eq:spmcomp1}) that finds the spare
provision matrix $\MAT{G}^{[A]}$ is replaced by
$\MAT{G}^{[D]}$, where   
%
%This formulation can be used
%for either Model A or B in \S\ref{sec:U2} and~\ref{sec:minU3}
%
\begin{equation}
  \label{eq:jenga1}
  \MAT{G}_k^{[D]} = {\MAT{Q}^k}^{T} \MAT{M} \MAT{U}_k,\quad 1\leq k\leq K.
\end{equation}  

The $k$-th column vector $\MAT{G}_k^{[D]}=\{g_{lk}\}_{L\times 1}$ in
$\MAT{G}^{[D]}$ is determined by the $k$-th
column vector $\MAT{U}_k=\{u_{rk}\}_{R\times 1}$ 
of the failure matrix $\MAT{U}$ in~(\ref{eq:flowf1}), 
the demand matrix
$\MAT{M}$, and the backup path matrix $\MAT{Q}^k$. 
The backup path matrix $\MAT{Q}^k$ indicates backup paths 
for all flows upon failure $k$.  In this way, each flow could have
more than one backup routes, one for each failure cases its working
path might encounter.  
Note, the FD path restoration approach has
many more backup path design variables than FID. 

\subsection{Stub Release}
\label{sec:fdstub}
When a working path is disconnected due to a failure, some of its links
might still reserve bandwidth which do not carry traffic anymore.  
Releasing this  bandwidth to be reused by other backup paths is termed {\it stub release} and could further improve
bandwidth efficiency.  The drawback  of this process is the extra overhead involved in determining where the stubs are and signaling to 
release the capacity. Here we consider stub release for the FD path restoration approach.

A new backup path matrix $\MAT{\bar{Q}}^k$ is defined by its elements as
%It is based on backup paths matrix $\MAT{Q}^k$ that is found using
%the SSR algorithm for the failure dependent path restoration.   
%
\begin{equation}
  \label{eq:stubrelease}
  \bar{q}^k_{rl} = \left\{
    \begin{array}{l l}
      q^k_{rl} - 1, & p_{rl}=1, u_{rk} =1, f_{kl}\neq 1\\
      q^k_{rl}, &otherwise.  \\
    \end{array}
  \right . 
\end{equation}

In this equation, the stub release function is represented by adding
``$-1$'' to the 
appropriate positions in the backup paths matrix $\MAT{Q}^k$.
The working capacity of flow~$r$ on link~$l$ will be released only when
its working path uses this link ($p_{rl}=1$); 
failure scenario~$k$ disconnects its working path ($u_{rk}=1$); and
 failure $k$ does not affect this link ($f_{kl} \neq 1$).
The matrix $\MAT{\bar{Q}}^k$ replaces $\MAT{Q}^k$
to find $\MAT{G}$ in~(\ref{eq:jenga1}). 
Since the working capacity released by the stub release function
depends only on failures, the  SSR 
algorithm is unchanged.  This allows stub release to be
implemented as a pluggable option in the SSR algorithm.

\section{Numerical Results}
\label{sec:results}




Numerical studies of the proposed SCA models and their associated SSR algorithms were conducted for a variety of scenarios on a set of nine different  networks.
The top and bottom layer topologies of the  networks  studied are shown 
in Fig.~\ref{fig:twolayertopo5} and~\ref{fig:net1}--\ref{fig:net8}. 
The number of links, nodes and traffic flows in the two
layers are summarized in 
Table~\ref{tbl:top} and~\ref{tbl:bottom} respectively. Two  top layer topology cases were studied:  full
mesh and partial mesh.  
In the full mesh case, all top layer nodes are
directly connected to all other top layer nodes. 
In the partial mesh case, the top layer has a sparser interconnection with the
topology given  in Fig.~\ref{fig:twolayertopo5} and Fig.~\ref{fig:net1}--\ref{fig:net8}.
 
%\item
%In numerical study, flows and links are symmetric so
%the problem is modeled in an undirected graph.  
%Note that neither the models nor the SSR algorithm has this
%limitation.

%\item 
The traffic flows on both layers were a  full mesh, each with unit traffic
demand.  
The assumption of full-meshed flows exposes any possible 
spare capacity sharing opportunities among all node pairs.  
The unit flow bandwidth is based
on the previous studies in the literature. Furthermore, our earlier
work on the single layer SCA~\cite{liu:dissertation} 
did not show a significant impact on the network redundancy by varying
the traffic distribution. 
The demand matrix in the top layer is given as
$\MAT{M}=\MAT{I}_{R\times R}$, where $R$ is the number of
flows.  In this case, $R=N(N-1)/2$ for a full mesh of flows, 
with $|N|$ denoting the number of nodes.
The demands in the bottom layer have a similar formulation with
superscript $^b$ on their variables.
The working paths are the shortest hop paths in both layers.  
These working paths have at least one failure-disjoint backup path. 

The total working capacity in the bottom layer reserved by the top
layer working paths is $W =
\MAT{e}^T \MAT{P} \MAT{H} \MAT{e}$, where $\MAT{P}$ is the working path
matrix in the top layer and $\MAT{H}$ is the interlayer link
incidence matrix.  
The failure scenarios considered were all single bottom layer link failures.
Hence, 
the bottom layer failure
matrix $\MAT{F}^b = \MAT{I}_{L^b\times L^b}$, where $L^b$ is the
number of the bottom-layer links.


%\item
%The SCA models are tailored to find backup paths so the total spare capacity is minimized for these traffic flows.

The following SCA models were studied.

\begin{itemize}

\item
The SCA model in the bottom layer protection as discussed in
\S\ref{sec:bottomonly}.  
%The traffic flows studied are full meshed unit
%traffic flows on the bottom layer.  
%This result is very similar to our previous work in~\cite{liu:ton05}. 



\item
The FID path restoration case
for both Models~A and~B for top layer protection 
in \S\ref{sec:MinU}. 
%Any single bottom layer link failures are protected.


\item 
The SCA model for  common pool protection at both layers in
Model~C in \S\ref{sec:bothlayer}.  
%Both layers are resilient to any single bottom layer link failures.

%The total spare capacity results are computed for the common pool
%survivability. 
%These results are compared with two separate single layer protection
%schemes, namely:
%top layer protection using Model~B; 
%and  bottom layer protection using the single layer SCA model 
%as in \S\ref{sec:bottomonly}.

\item The FD path restoration at the top layer scheme in
section~\ref{sec:fd}.

\item The FD path restoration at the top layer with 
the stub release feature in \S\ref{sec:fdstub}.

\item Finally, the above SCA models protecting any single bottom layer
node failure were studied.

\end{itemize}


The numerical results for the SCA models are given in Tables~\ref{tbl:top} - Table~\ref{tbl:FD2}.
Two algorithms, 
 branch and bound (BB) and 
SSR, 
were used to find the solutions to the SCA models.  Since the SSR
solution depends in part on the ordering of the flows, a range of  
 solutions from 64 random cases are listed with the format of the
minimum and the maximum results between a hyphen ``-''.  
The execution time results reported for the SSR algorithm are
the total time to find the entire 64 solutions. 
The BB results are obtained from the 
commercial software CPLEX which could find the optimal solution.  Note, that in the Tables, some cases for Network~8 are marked with a `-' in the BB column indicating that no results were obtained for during the execution time limit of 5 days.

The results for the bottom layer SCA are  provided in Table~\ref{tbl:bottom}. Note, that the bottom layer results are the same regardless of the partial/full mesh layout of the top layer.
Notice, that the SSR results are very close to the BB results while typically having a faster execution time. 

The spare capacity required for the top layer restoration approach  ($S^{[A]}$ or $S^{[B]}$), and the SCA solution time are provided in Table~\ref{tbl:top}. 
%From the results one can see that having a partial mesh topology at the top layer has greater spare capacity requirement when compared with the full mesh results. For example consider Network~6, where $S^{[A]}$ This is due to a partial mesh having less opportunities for backup path bandwidth sharing. 
Again one can see that the SSR algorithm provides near optimal results with lower execution speeds. 

In Table~\ref{tbl:twolayer}, the results for the SCA problem for  common pool protection at both layers in Model~C is provided.  The second column, $W^b+W$, provides the total working capacity used by working paths on both layers in the network.  The third column,  $S^b+S^{[B]}$, list the best total spare capacity when both layers find their SCA solution using Model~B individually.  
%In this case, the spare provision matrix between two layers are not shared.  
In the next two columns, the results of the total spare capacity, $S^{[C]}$, for  common pool protection using Model~C are provided.  The solution time values are listed in the next two columns. 

Table~\ref{tbl:FD2} presents the results for the FD and
FD with stub release cases for top layer path
restoration using SCA Model~A. 
Note, only SSR results are given here.

%These numerical results are visualized partly as Figure~\ref{fig:spare1to4} to~Figure~\ref{fig:redundancy}. They are summarized as follows: 
Considering all the numerical results  several interesting observations can be made as follows. 

\subsection{SSR versus branch and bound solutions}

\begin{enumerate}
\item  SSR finds a \emph{near} optimal solution for all cases.  
Among all numerical results, the minimum spare capacity found by SSR
is typically near or the same as  the optimal solution  found by BB. 
%This biggest gap in all cases for the total spare capacity $S$ between
%BB and SSR  
%is in the case of using Model A for the full mesh type in
%Network~4 of Table~\ref{tbl:top}. 
 Most results have gaps smaller than
5\% .

\item  SSR scales well in comparison to BB. 
 Among all numerical cases, SSR is typically much faster than BB and
is always able to find a solution well within the maximum execution
time limit (5 days). In contrast for large networks (e.g., Network~8),
the BB algorithm takes a great amount of solution time and in some
cases is unable to find a solution within the maximum time limit. 
 
%BB takes various time up to 4.8 days in the first 7 networks and
%did not find optimal solutions in several large cases on Network~8.  

\end{enumerate}

Hence, it might be a good compromise to use SSR as a fast algorithm to
find a solution for large networks. 
%while using branch and bound based approach to discover the
%optimal solution over a longer period.

\subsection{Top layer cross-layer spare capacity reservation}

%\item  
From the results of Table~\ref{tbl:top} comparing Model B with Model A one can see the cross layer spare capacity reservation in Model~B has very small
gain in the bandwidth.  
Comparing the best results in the total spare capacity between Model~A
and~B for top-layer protection, the results in the $S^{[B]}$ column
are about 1\%, on average, less than those in  the $S^{[A]}$ column.  
These results indicate  that Model~B is suitable for an
off-line  traffic engineering to further improve bandwidth
efficiency as the small benefits
 might not justify an online implementation in
the GMPLS control plane. 
Since Model~B requires the top-layer backup route to be able to
reserve the bottom-layer link spare capacity.   
This cross layer reservation is expensive in terms of the information
exchanged between two neighboring layers.
%It might not be justified from the small spare capacity savings
%achieved using Model~B.  

\subsection{Common pool protection vs. single layer protection on
both layers}

%The results shows that the common pool protection reduces the total
%spare capacity for about 2--20\% comparing to protection at both layers separately.

%As described earlier, both layers have full mesh traffic flows.  Each
%flow has single unit of traffic demand.  
%This flow configuration is applied to both the common pool model in Model~C,
%the top-layer SCA in Model~B,  and the bottom-layer SCA model. 
Comparing the results of the common pool approach versus having separate independent protection schemes on each layer one can see some clear differences in the results.
Drawing on the data from Table~\ref{tbl:top} and Table~\ref{tbl:twolayer} one can construct Fig.~\ref{fig:spare1to4} and~\ref{fig:spare5to8} to compare the two approaches.
In the Figures the total spare capacity results on eight networks are plotted as bar
charts. The network numbers are used as the X axis. 
Each network has two groups of bars.

\begin{itemize}
\item
The first group contains two bars to the left of the network number
on the X axis.  They are results from the partial mesh top-layer topology.
\item
The second group of two bars are to the right of the network number.
They are results from the full mesh top-layer topology.   

%Within each group of bars,  the first bar is stacked in the left and the
%third one is stand-alone in the right.

\item 
Within each group of bars, the leftmost bar is split into two stacked components showing the amount of spare capacity reserved by the two independent layers. The  bottom bar indicates the value of the total spare capacity in the
bottom-layer $S^b$.  
The  top bar indicates the total spare capacity reserved in the bottom
layer for the top-layer protection using Model~B, i.e. $S^{[B]}$.
\item 
Also, within a group of bars, the rightmost bar indicates the total spare capacity in both
layers using the common pool protection, i.e. $S^{[C]}$.
\end{itemize}

One can clearly see that common pool protection uses less spare capacity
than the total of the two single layer protection schemes.  
The percentage savings in the total spare capacity using 
common pool protection can be  computed as
\begin{equation}
\delta = \frac{S^b + S^{[B]} - S^{[C]}}{S^{[C]}}.
\end{equation}
Fig.~\ref{fig:save} plots the percentage savings for the eight networks for both the full mesh and partial mesh cases. The figure shows that
 the common pool approach  can  yield a  total spare capacity reduction in the range of  2--20\%.  

\subsection{Network redundancy and scalability}

Fig.~\ref{fig:redundancy} plots the network redundancy values  ($S/W$)
achieved using  the various SCA models.  
%Similar to Fig.~\ref{fig:spare1to4} and~\ref{fig:spare5to8}, 
%it is also a bar chart showing redundancy
%values for  both partial and full mesh top-layer topologies on eight
%networks.  
The group of bars to the left of a network number are for the
partial mesh top-layer topology while the bars to the right are for the
full mesh case.   Notice that within a group,
the redundancy bars for the top layer and the bottom layer are plotted
stand-alone instead of stacked together.  This is because  the two layers
have different  working capacity values, thus, their redundancy values
cannot be added together.  

The first observation  is that the network redundancy values at the top
layer are always larger than those at the bottom layer.  
One explanation for this comes from the fact that
less traffic flow in the top-layer protection produces
 less chance to share spare capacity on their backup routes.  
The other explanation is that the top-layer traffic have to be routed
over top-layer links, then mapped down to the bottom layer.  
This mapping  reduces the chance of spare capacity sharing, 
and consequently increases the network redundancy.
%Co-examining Figure~\ref{fig:spare1to4} and~\ref{fig:spare5to8},
%we could notice that
%the total spare capacity values in the top-layer models are
%always smaller than those in the bottom-layer ones.  
%Meantime, their working capacity values are also smaller.  So the
%smaller traffic amount at the top layer might not be the major
%contribution to the larger redundancy at the top layer. 
%Especially when both layers have full mesh traffic flows.  
The second observation is that the common pool protection
scheme has   redundancy  values similar to  bottom
layer only protection.  
This is important for the scalability of  common pool protection 
on multi-layer networks.  
%In the case where the traffic flows at the top layer network increase,
%the common pool approach might maintain its redundancy at relatively
%same level or one that increasing slowly. 


% yliu: FOLLOWING IS IN DRCN05. I FEEL IT IS NOT QUITE USEFUL TO COMPARE TIME IN DETAIL.  SO DELETE THEM

%From the results in Table~\ref{tbl:all}, one can see that the SSR
%algorithm closely approximates the optimal BB solution. 
%In network 0,
%both BB and SSR find the optimal solutions for both 
%models.  
%In the other 8 networks, 
%the SSR results using Model B have a slightly smaller range for the solution 
%than those found from Model A.  
%This indicates the spare capacity can be reduced in Model B, but
%the reduction is very small -- less than 5\% when using Model B solved by either BB or SSR.
%
%The CPU time to find the optimal solution depends on 
%both the network size and topology.
%SSR can find all 64 solutions in
%less than 30 seconds in all cases except network 8, where SSR finds solutions in minutes while BB could not find solutions after two days.  
%In most cases with the combinations of top-layer, bottom-layer topologies and the SCA models, BB has shorter time than SSR.
%There are 10 out of these total 34 cases where SSR has shorter time than BB.
%For example, when using the model A on network~6 with full mesh demands, it takes about 20 minutes to get the optimal results in BB but 3 seconds in SSR. 
%In addition, when using the model B on network~8 with full mesh demands, BB could not find a solution after 2 days while SSR uses about 4 minutes.
%BB performs very fast on most cases.  It indicates that the optimal solution could be found quickly in CPLEX v9 in certain cases.
%However, this fast speed is not guaranteed.  
%It might take much longer time, such as on network~8.  Using model A, it takes about 2353 seconds for BB to find the optimal solution while it takes 8.16 seconds for SSR to obtain a next optimal solution.  Using Model B, BB could not find an optimal solution after 2 days.
%In addition, BB is known for worse scalability on large networks. 
%For these reasons,
%SSR could be a good alternative for SCA on large networks.


%Comparing the total spare capacity between full meshed and partial
%meshed top-layer links, it is clear that partial mesh requires more spare
%capacity.  It is because backup route might take longer routes at
%the bottom layer due to the short of direct top-layer links on the partial
%mesh top layer.  However, this could save top-layer cost such as
%router interface cards in an IP over WDM network.  From the data, it
%is also shown that the percentage of additional total spare capacity
%in a partial mesh decreases when the network get larger.  In small
%networks such Net~1 and~2, the partial mesh requires $\approx 100\%$ 
%more total spare capacity than the full mesh.  
%On Network~6 and~7, the percentage reduced to 

\subsection{FD path restoration schemes and stub release}

In Table~\ref{tbl:FD2}, we use Model~A and the SSR algorithm 
to compare various path restoration schemes, 
i.e. FID, FD, and FD with Stub Release (FDStubR),
to protect either single link or single node failures. 
%
% WHY DID YOU USE MODEL A INSTEAD OF B???
Model~B is not used in this comparison because of its requirement of a
cross-layer capacity reservation protocol and the small
gain in the total spare capacity observed in the previous results.

The numerical results using partial mesh top layer on six networks 
are shown in Table~\ref{tbl:FD2}. 
The best results in all cases are normalized by their FID results 
on the same network and plotted in 
Fig.~\ref{fig:FDLink} for link protection and
Fig.~\ref{fig:FDNode} for node protection.  
In these two figures, the network number is shown in the X axis.
The normalized total spare capacity percentage values,
for FID, FD, and FDStubR, are drawn as three
bars above the network number.
The values of FID are always equal to 100\%  since FID
values are used as the base in the normalization. 
One can see that  
FD path restoration has about 10--30\% 
lower total spare capacity values 
than those of FID using link protection.
This indicates that multiple backup paths 
in FD path protection could increase 
the chance of spare capacity sharing, 
and consequently, reduce network redundancy.  
Using FD path restoration scheme with stub release
(FDStubR), 
the total spare capacity can be further reduced by 1--10\% 
from those in FD.
In node protection, similar to the link protection above,
FDStubR could provide the lowest redundancy while FD is slightly
higher than FDStubR and about 4--35\% lower than the FID results.  
It is important to be aware that the smaller spare capacity values in
node protection does not necessarily indicate a better bandwidth
efficiency than link protection.  
The smaller value could come from the dropped demands that cannot be
recovered at the failure of their end nodes.  
%On the contrary, link
%failure can guarantee that 100\% of the dropped demands can be
%recovered on 2-connected networks.  
%In addition, node protection in two-layer networks might require
%different interlayer mapping other than that used in link protection
% in order to
%prevent the single node failure at the bottom layer to partition the
%top layer network.  This also makes such a comparison lose of a common
%base. 
%This is the reason we did not provides results for the Network~6 and~8 since they requires different interlayer mappings.

\section{Conclusions}
\label{sec:conc}

In this paper, several variations of the
SCA problem  for two-layer networks are
formulated as ILP models. 
 Specifically, we present SCA models for protection at the bottom layer only, protection at the top layer only, protection at the top layer only with cross layer sharing of spare capacity and common pool cross layer protection. The extension of these models to failure dependent path restoration with and without stub release are also presented. 
A fast routing based heuristic termed successive survivable routing (SSR) was proposed for solution of the SCA models.
Numerical results show that the SSR algorithm can be used to efficiently find near optimal solutions.

Comparison numerical studies show that it might not be cost
effective to reserve spare capacity across two layers using only a top layer restoration scheme as the bandwidth gains are small.  
In contrast when   common pool protection is compared against
using single layer protection schemes at both the top layer and bottom layer, major spare capacity savings are possible. 
%The numerical results for sample networks indicate  spare capacity savings of 2--20\%.  
The common pool protection scheme also maintains its network
redundancy across increasing network size, indicating
good scalability.  
%In particular in MPLS VPN deployments or GMPLS networks, 
%a large number of top-layer networks might be deployed 
%on a backbone network.  
%In this case, the common pool protection scheme could save a significant amount of
%spare capacity while meeting survivability requirements.
 

\appendix 
%{Survivable topology layout model}
\label{sec:findH}
The survivable topology layout problem is modeled in the following. 
As described in \S\ref{sec:sca},
the two-layer link incident matrix $\MAT{H}$ should guarantee that
any single bottom-layer link failure will not partition the top layer.   
%This property is called \emph{immunity from failure propagation}.  
Each pair of nodes at the top layer must  have at least two paths which have disjoint bottom-layer links.  
This property is a special type of two-connectivity.  
It is called two-bottom-layer-link-connectivity and has been discussed by Modiano and Narula-Tam
in~\cite{modiano01:survtopo}.  
In the following, a matrix model is given to extend
their model to find the
survivable top-layer topology that can be resilient to an arbitrary set of 
failure scenarios at the bottom layer. The basic formulation is given below.
\begin{eqnarray}
  \label{eq:minH}
  \min_{\MAT{H}} & \MAT{e}^T \MAT{H e} \\
  s.t. &   \label{eq:massbalH}
   \MAT{H} {\MAT{B}^b}^T = [ \MAT{B}^T | \MAT{0} ] \\
  & \label{eq:u2conn}
  \MAT{C} \MAT{H}_f < \MAT{C e} \\
  & \label{eq:HF}
  \MAT{H}_f = \MAT{H} \btimes {\MAT{F}^b}^T 
\end{eqnarray}

The objective (\ref{eq:minH}) is to minimize the total number of bottom-layer
links used by all top-layer links.  This objective can be easily
extended to consider cost, bandwidth, etc..
The flow conservation constraint in~(\ref{eq:massbalH}) requires the
top-layer link to map to a bottom-layer path.
The zero matrix $\MAT{0}$ in the right hand side 
has the dimensions of $L\times (N^b -N)$.
It is used to fill up the matrix equation for  
the nodes that appear only at the bottom layer but not at the top layer.  
These nodes have indexes $n$, where  $N < n\leq N^b$.

A topology is survivable if and only if its cut-set matrix
of the top-layer topology $\MAT{C}$
follows constraint (\ref{eq:u2conn}), where the matrix $\MAT{H}_f$
is calculated from the layout information matrix $\MAT{H}$ and the bottom-layer
failure matrix $\MAT{F}^b$ in~(\ref{eq:HF}).  
The operator ``$<$'' in~(\ref{eq:u2conn})  means that each element in the
vector on the right hand side 
is greater than any elements in the corresponding row of the matrix on
the left hand side.  
%This operation is similar to the alternative format $\MAT{s}\ge\MAT{G}$
%in~(\ref{eq:pickmax2}). 

When the lower layer failure matrix $\MAT{F}^b$ considers all single
link failures, this model is equivalent to the model
in~\cite{modiano01:survtopo}.  
The \emph{cut-set matrix}  
\index{cut-set matrix} 
$\MAT{C}=(c_{ij})$ of a graph $G$ has elements
$c_{ij}=1$ if the $i$-th cut-set of $G$ contains the edge $e_j$, and
$c_{ij}=0$ otherwise.   
This matrix is defined in~\cite{foulds92:graph}.
The number of rows in $\MAT{C}$ is the total
number of cut-sets in graph $G$, and equals to $2^{N-1}$.  
Due to this exponential term, this model has exponential number of
constraint~(\ref{eq:u2conn}) and it cannot scale with the number of
top-layer nodes.  A heuristic algorithm  for determining $C$ has been discussed
in~\cite{modiano01:survtopo}.  In this paper, we used the solution $\MAT{H}$
of the above extended formulation solved by the branch and bound solver CPLEX. 

For the case of node failure at the bottom layer, the constraint~(\ref{eq:HF})
has to be modified.  A bottom node failure can disconnect the source or
destination nodes of a top-layer link in the topology.  
%These node failures can completely disconnect
%any cut-sets that contain only one node.  
To overcome this difficulty, we remove any cut-sets that
contains one node in one of its partitioned subgraph from $\MAT{C}$ in
constraint~(\ref{eq:HF}).  
Meantime, the bottom-layer topology has to be 2-node-connected. 
For  general failures at the bottom layer, this cut-set model may have difficulty in finding a unique interlayer matrix $\MAT{H}$.  This is a topic of the on-going research, such as the generalized failure-cut in~\cite{farago:if06}.
% \cite{inria:DavidCondert}
% or probe allocation in~\cite{zang:itc19}.  
%In the numerical study followed, this method fixes the difficulty and 
%finds correct topology layout to survive any bottom-layer node failures.

%Another important future work is to combine the survivable topology
%layout problem with the SCA problem.  This might achieve better
%solution quality but hard to scale in large size networks. 

\bibliographystyle{IEEE}

% Original bib file
%\bibliography{dis}
\begin{thebibliography}{10}

\bibitem{vasseur:survive}
J.~Vasseur, M.~Pickavet, and P.~Demeester,
\newblock {\em Network Recovery: Protection and Restoration of Optical,
  SONET-SDH, IP and MPLS},
\newblock Morgan Kaufmann MKP, 2004.

\bibitem{grover:survive}
Wayne Grover,
\newblock {\em Mesh-based Survivable Networks: Options and Strategies for
  Optical , MPLS, and ATM Networking},
\newblock Prentice Hall PTR, 2003.

\bibitem{pioro:survive}
M.~Pioro and D.~Medhi,
\newblock {\em Routing, Flow, and Capacity Design in Communication and Computer
  Networks},
\newblock Morgan Kaufmann MKP, 2004.

\bibitem{corchat00:ton}
O.~Crochat, J.-Y.~Le Boudec, and O.~Gerstel,
\newblock ``Protection interoperability for {WDM} optical networks,''
\newblock {\em IEEE/ACM Transactions on Networking}, vol. 8, no. 3, pp.
  384--395, June 2000.

\bibitem{modiano01:survtopo}
E.~Modiano and A.~Narula-Tam,
\newblock ``Survivable routing of logical topologies in {WDM} networks,''
\newblock in {\em Proceeding of IEEE INFOCOM}, Apr. 2001.

\bibitem{kurant:survrout}
M.~Kurant and P.~Thiran,
\newblock ``On survivable routing of mesh topologies in {IP-over-WDM}
  networks,''
\newblock in {\em Proceeding of IEEE INFOCOM}, 2005.

\bibitem{ducatelle:global04}
F.~Ducatelle and L.~M. Gambardella,
\newblock ``{FastSurv}: A new efficient local search algorithm for survivable
  routing in {WDM} networks,''
\newblock in {\em Proceeding of IEEE Global Communications Conference}, Dallas,
  TX, USA, Nov. 2004.

\bibitem{giroire:infocom03}
F.~Giroire, A.~Nucci, N.~Taft, and C.~Diot,
\newblock ``Increasing the robustness of {IP} backbones in the absence of
  optical level protection,''
\newblock in {\em Proceeding of IEEE INFOCOM}, 2003.

\bibitem{xu:netmag04}
D.~Xu, Y.~Xiong, C.~Qiao, and G.~Li,
\newblock ``Failure protection in layered networks with shared risk link
  groups,''
\newblock {\em IEEE Network}, pp. 36--41, May 2004.

\bibitem{Demeester:commag99}
P.~Demeester and M.~Gryseels,
\newblock ``Resilience in multilayer networks,''
\newblock {\em IEEE Communications Magazine}, vol. 37, no. 8, pp. 70--76, 8
  1999.

\bibitem{Sahasrabuddhe:jsac02}
L.~Sahasrabuddhe, S.~Ramamurthy, and B.~Mukherjee,
\newblock ``Fault management in {IP-Over-WDM} networks: {WDM} protection versus
  {IP} protection,''
\newblock {\em IEEE Journal on Selected Areas of Communications}, vol. 20, no.
  1, pp. 21--33, Jan. 2002.

\bibitem{Zheng:comnet06}
Q.~Zheng and G.~Mohan,
\newblock ``Multi-layer protection in {IP-over-WDM} networks with and with no
  backup lightpath sharing,''
\newblock {\em Computer Networks}, vol. 50, pp. 301--316, Jan. 2006.

\bibitem{Koo:icc03}
S.~Koo, G.~Sahin, and S.~Subramaniam,
\newblock ``Cost efficient {LSP} protection in {IP/MPLS-over-WDM} overlay
  networks,''
\newblock in {\em Proceeding of IEEE International Conference on
  Communications}, June 2003, pp. 1278--1282.

\bibitem{Ou:jsac03}
C.~Ou, K.~Zhu, H.~Zang, L.~Sahasrabuddhe, and B.~Mukherjee,
\newblock ``Traffic grooming for survivable {WDM} networks -- shared
  protection,''
\newblock {\em IEEE Journal on Selected Areas of Communications}, vol. 21, no.
  9, pp. 1367--1383, Nov. 2003.

\bibitem{liu:ton05}
Y.~Liu, D.~Tipper, and P.~Siripongwutikorn,
\newblock ``Approximating optimal spare capacity allocation by successive
  survivable routing,''
\newblock {\em IEEE/ACM Transactions on Networking}, vol. 13, no. 1, pp.
  198--211, Feb. 2005.

\bibitem{kolman96:disc_math}
Bernard Kolman, Robert~C Busby, and Sharon Ross,
\newblock {\em Discrete Mathematical Structures},
\newblock Prentice Hall, 1996.

\bibitem{iras98}
R.~Iraschko, M.~MacGregor, and W.~Grover,
\newblock ``Optimal capacity placement for path restoration in {STM} or {ATM}
  mesh survivable networks,''
\newblock {\em IEEE/ACM Transactions on Networking}, vol. 6, no. 3, pp.
  325--336, June 1998.

\bibitem{Xiong:TON99}
Y.~Xiong and L.~G. Mason,
\newblock ``Restoration strategies and spare capacity requirements in
  self-healing {ATM} networks,''
\newblock {\em IEEE/ACM Transactions on Networking}, vol. 7, no. 1, pp.
  98--110, Feb. 1999.

\bibitem{liu:drcn01}
Y.~Liu and D.~Tipper,
\newblock ``Spare capacity allocation for non-linear cost and failure-dependent
  path restoration,''
\newblock Third International Workshop on Design of Reliable Communication
  Networks (DRCN), Budapest, Hungary, October 7--10 2001.

\bibitem{liu:dissertation}
Yu~Liu,
\newblock {\em Spare capacity allocation method, analysis and algorithm},
\newblock {Ph.D.} dissertation, School of Information Sciences, University of
  Pittsburgh, 2001,
\newblock \url{http://www.sis.pitt.edu/~yliu/dissertation/}.

\bibitem{foulds92:graph}
L.~R. Foulds,
\newblock {\em Graph Theory Applications},
\newblock Universitext. Springer-Verlag, 1992.

\bibitem{farago:if06}
Andras Farago,
\newblock ``A graph theoretic model for complex network failure scenarios,''
\newblock in {\em The Eighth INFORMS Telecommunications Conference},
%  \url{http://telecom.section.informs.org/conference/16619.pdf}, 
Mar. 2006.

\end{thebibliography}

\begin{biography}
{\bf Yu Liu} (S'96-M'02) received the B.E. degree in information science and technology
from Xi'An Jiaotong University, China, in 1993, the M.E. degree in
communications and electronic systems from Tsinghua University, China, in 1996,
and the Ph.D. in telecommunications from the University of
Pittsburgh, Pittsburgh, PA, in 2001.  
He joined OPNET Technologies in August 2001 and is currently a senior software engineer in network design and optimization.
 
His research interests include network design, performance and
analysis, mathematical programming, queueing theory, embedded systems,
and distributed systems. 
At OPNET, he is developing automated design solutions 
for IP/MPLS networks, such as traffic engineering, fast reroute
deployment, link dimensioning, topology design, multi-layer network
design, and capital expenditure optimization 
in the IT~Guru/SP~Guru Network Planner products. 
\end{biography}

\begin{biography}
{\bf David Tipper} (S'78-M'88-SM'95) received the B.S.E.E. degree from Virginia Tech, M.S.S.E and Ph.D.E.E. degrees from the University of Arizona. He is an Associate Professor in  the
Telecommunications Program with a secondary appointment in the Electrical
Engineering Department at the University of Pittsburgh. Prior to joining Pitt in 1994, he was an Associate Professor in the Electrical and Computer Engineering Department at Clemson University. His current research interests are network design and traffic restoration procedures for survivable networks, infrastructure protection, network control techniques and performance analysis. He is the co-author of the textbook {\it The Physical Layer of Communication Systems} published by Artech House in 2006. Also, he is a  co-editor of the book {\it Information Assurance: Survivability and Security in Networked Information Systems}, to be published by Elsevier/Morgan Kaufmann in 2007. 
\end{biography}

\begin{biography}
{\bf Korn Vajanapoom} received the B.E. degree in Electrical Engineering from Chulalongkorn University, Thailand, in 1998, and the M.S. degree in Telecommunications from the University of Maryland, College Park, in 2002. He is currently working toward the Ph.D. degree in Telecommunications at the University of Pittsburgh, Pittsburgh, PA.
From 1998 to 1999, he was an engineer at the Department of International Telephone, Communications Authority of Thailand (CAT). 
His research interests include incremental survivable network design, 
availability analysis in survivable networks, and multi-layer network 
survivability.
\end{biography}


%\end{document}

\newpage 


\begin{table*}[!htbp]
  \begin{center}
    \caption{Results of two top-layer spare capacity allocation (SCA) }
    \label{tbl:top}
{ %\scriptsize
    \begin{tabular}{c |c|c|c| c| c|c|c|c| c|c|c|c }
\hline  \hline
    & \mc{8}{|c}{Top Layer Only}  & \mc{4}{|c}{Time (second) } \\
\cline{2-13}
net & $N$ & $L$ & $R$ & $W$ & \mc{2}{|c}{$S^{[A]}$} & \mc{2}{|c}{$S^{[B]}$} & \mc{2}{|c}{$S^{[A]}$} & \mc{2}{|c}{$S^{[B]}$} \\
\cline{6-13}
    &     &     &     &     & BB & SSR & BB & SSR & BB & SSR & BB & SSR \\
\hline 
\mc{13}{l}{Full mesh top layer} \\
\hline
0$^\dagger$ 
  & 4 & 6 & 6 & 9 &  11 & 11-13 & 11 & 11 & 0.01 & 0.73 & 0.01 & 0.75 \\
\hline
1 & 6 &15 &15 & 27&  15 & 16-22 & 15 & 16-22 & 0.07 & 0.81 & 0.08 & 1.00  \\
\hline
2 & 7& 21& 21 & 39 & 28 & 30-37 & 28 & 29-35 & 4.09 & 0.88 & 0.54 & 1.34  \\
\hline 
3 & 8& 28& 28 & 63 & 39 & 40-53 & 37 & 40-49 & 29.37 & 0.98 & 1.09 & 1.94  \\
\hline
4 & 10& 45& 45& 106 & 48 & 56-68 & 48 & 54-68 & 88.04 & 1.67 & 11.98 & 5.36  \\
\hline 
5 & 10& 45& 45 & 134& 121& 129-141& 118 & 124-131& 56.53 & 1.53 & 64.49 & 4.26 \\
\hline
6 & 10& 45& 45 & 157 & 121 & 132-147 & 117 & 125-135  &1,145 & 1.69 & 290 & 7.23 \\
\hline
7 & 8& 28& 28 & 116 & 103 & 103-130 & 102 & 105-111& 1.07 & 1.11 & 3.54 & 2.66 \\
\hline 
8 & 12& 66& 66& 309& 217 & 230-251 & - & 221-253 & 2,353 & 4.48 & 2day & 40.19 \\
\hline 
\mc{13}{l}{Partial mesh top layer} \\
\hline
1 & 6& 9& 15  & 34 &  32 & 32-35 & 31 & 32-33 & 0.03 & 0.81 & 0.04 & 0.95 \\
\hline
2 & 7& 12& 21 & 54 & 45 & 46-50 & 45 & 46-50 & 0.06 & 0.86 & 0.07 & 1.17 \\
\hline 
3 & 8& 14& 28 & 72 & 49 & 49-57 & 48 & 49-57 &  0.1 & 0.89 & 0.17 & 1.36 \\
\hline
4 &  10& 16& 45& 136 & 97 & 98-103 & 97 & 98-104 & 0.34 & 1.16 & 0.29 & 2.34 \\
\hline
5  & 10 & 18 & 45 & 157& 114& 115-125& 114 & 115-123 & 0.55 & 1.09 & 4.29 & 2.44  \\
\hline
6 & 10 & 22 & 45 & 184 & 162 & 164-172 & 160 & 161-170 & 1.12 & 1.19 & 0.71 & 3.19 \\
\hline
7  & 8& 13& 28 & 126 & 100 & 100-108 & 100 & 100-111 & 0.34 & 0.97 & 1.37 & 1.89 \\
\hline
8  & 12& 24& 66 & 389& 320 & 323-339 & 320 & 323-338 & 1.9 & 2.08 & 2.61 & 13.25  \\
\hline 
\hline
\mc{13}{l}{$\dagger$: {\small Network 0 is shown in Fig.~\ref{fig:twolayertopo5}.} }
    \end{tabular}
}
  \end{center}
\end{table*}

\begin{table}[!htbp]
  \begin{center}
    \caption{Results of bottom-layer spare capacity allocation (SCA) }
    \label{tbl:bottom}
{ \scriptsize
    \begin{tabular}{c |c|c|c| c|c|c | c|c }
\hline  \hline
net & $N^b$ & $L^b$ & $R^b$ & $W^b$ & \mc{2}{|c}{$S^b$} & \mc{2}{|c}{Time (Second)} \\
\cline{6-7}
&  &  & & &  BB$^1$ & SSR$^2$ & BB & SSR \\
\hline 
\hline
0 & 5 & 7 & 10 & 13 & 11 & 11 & 0.01 & 0.78 \\ 
\hline
1 & 10& 22& 45 & 71 & 23 & 26-31 & 36 & 1.2 \\
\hline
2 & 12& 25& 66 & 112& 51 & 53-58 & 14 & 1.5 \\
\hline 
3 & 13& 23& 78 & 162& 67& 71-77 & 43 & 1.7 \\
\hline
4 & 17&31& 136 & 320& 124 &126-137 & 2.8hr & 3.4 \\
\hline 
5 & 18& 27& 153& 413& 242& 243-252 & 10.46 & 3.0 \\
\hline
6 & 23& 33& 253& 835& 563& 569-582 & 52.07 & 5.5 \\
\hline
7 & 26&30&325& 1366& 901& 920-931 & 5.78 & 6.5 \\
\hline 
8 & 50& 82&1225 & 5552&-&2863-2896   & - & 156\\
\hline 
\hline
    \end{tabular}

    \begin{tabular}{ p{0.45\textwidth} }
Note: 1) Branch and Bound (BB) results are from AMPL/CPLEX v9.10 on a Sun Fire V240 Server with 1GHz CPU and 2GByte memory.\\
2) SSR results are obtained on a Intel Pentium 4 1.5GHz CPU with 1GByte memory.  These results are shown as the range of 64 random cases in the format of ``min-max''.
    \end{tabular} 
}
  \end{center}
\end{table}


\begin{table}[!htbp]
  \begin{center}
    \caption{Results of combining two single-layer SCA and the common pool approaches }
    \label{tbl:twolayer}
{\scriptsize
    \begin{tabular}{c |c|c| c|c| c|c  }
\hline  \hline
    &  & Separate & \mc{4}{|c}{Common pool } \\
\cline{3-7}
net & $W^b+W$ & $S^b+S^{[B]}$ & \mc{2}{|c}{$S^{[C]}$} & \mc{2}{|c}{Time $S^{[C]}$} \\
\cline{3-7}
    &         & Best$^1$      & BB    & SSR  & BB & SSR \\
\hline 
\mc{7}{l}{Full mesh top layer} \\
\hline
0 &  22 & 22  & 19 & 19-19  & 0.02 & 1.49 \\
\hline
1 &  98 & 38  & 34 & 37-43  & 118  & 2.09 \\
\hline
2 & 151 & 79  & 73 & 77-84  & 9.95 & 2.70 \\
\hline 
3 & 225 & 104 & 97 & 101-110 & 18.91 & 3.48 \\
\hline
4 & 426 & 172 & 157 & 167-182 & 4.8day & 8.52 \\
\hline
5 & 547 & 360 & 336 & 349-362 & 212.22 & 6.74 \\
\hline
6 & 992 & 680 & 653 & 672-689 & 295.4  & 12.36 \\
\hline 
7 & 1482& 1004& 978 & 982-992 & 15.32 & 8.70 \\
\hline 
8 & 5861& 3084& - & 3033-3077 & -     & 182.28 \\
\hline 
\mc{7}{l}{Partial mesh top layer} \\
\hline
1 & 105 & 54  & 45 & 47-52 & 49.33 & 3.19 \\
\hline
2 & 166 & 96  & 82 & 85-90  & 3.17 & 3.55 \\
\hline
3 & 234 & 115 & 108& 111-119 & 88.89 &4.14 \\
\hline
4 & 456 & 221 & 192 & 201-213 &  1,115 & 6.55 \\
\hline
5 & 570 & 356 & 338 & 352-360 & 18.16  & 6.78 \\
\hline
6 & 1019& 723 & 657 & 678-695 & 256.9  & 9.64 \\
\hline
7 & 1492& 1001& 975 & 975-990 & 5.9  & 9.7 \\
\hline
8 & 5941& 3183 & - & 3045-3078 & -     & 156.61 \\
\hline
\hline
    \end{tabular}

    \begin{tabular}{ p{0.45\textwidth} }
Note: 1) Best solutions from BB and SSR results in previous Table~\ref{tbl:top} are listed here.  In most cases, BB provides the best solution.  However, when BB cannot find feasible solution, SSR results are used as the best solution here. 
    \end{tabular} 
}
  \end{center}
\end{table}


\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.45\textwidth]{fig2}
    \caption{Total Spare Capacity on two-layer networks on Network 1-4}
    \label{fig:spare1to4}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.45\textwidth]{fig3}
    \caption{Total Spare Capacity on two-layer networks on Network 5-8}
    \label{fig:spare5to8}
  \end{center}
\end{figure}
\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.45\textwidth]{fig4}
    \caption{Percentage Saving of the Total Spare Capacity using SCA on both layers}
    \label{fig:save}
  \end{center}
\end{figure}

\begin{figure*}[!htbp]
  \begin{center}
    \includegraphics[width=0.9\textwidth]{fig5}
    \caption{Redundancy on two-layer networks}
    \label{fig:redundancy}
  \end{center}
\end{figure*}


% Table 2

\begin{table}[!htbp]
  \begin{center}
    \caption{Comparison of $S^{[A]}$ for path restoration schemes}
    \label{tbl:FD2}
{\small
    \begin{tabular}{r | l | l | l}
\hline \hline
% Restoration & Link failure & Node failure \\
%\hline
% FID & 115--125 & 106--115\\
% FD & 104--118  & 97--109 \\
% FDStubR & 103--115 & 94 --107 \\
Net & FID & FD & FDStubR \\
\hline
\mc{4}{l}{Link Failure}\\
\hline
1 &  32-- 35 &  24-- 28 &  23-- 28 \\
2 &  46-- 50 &  32-- 39 &  28-- 35 \\
3 &  49-- 57 &  40-- 49 &  36-- 40 \\
4 &  98--103 &  75-- 85 &  71-- 78 \\
5 & 115--125 & 104--118 & 103--115 \\
%6 & 164--172 & 103--129 &  97--114 \\
7 & 100--108 &  78--108 &  75--101 \\
%8 & 323--339 &    --$^1$&    --$^1$\\ 
\hline
\mc{4}{l}{Node Failure}\\
\hline
1 &  23-- 25 &  22-- 26 &  20-- 25 \\
2 &  60-- 64 &  39-- 43 &  35-- 42 \\
3 &  37-- 44 &  30-- 38 &  28-- 37 \\
4 & 124--125 &  90-- 98 &  76-- 86 \\
5 & 106--115 &  97--109 &  94--107 \\
%6 &    --$^2$    &    --    &    --    \\
7 & 102--115 &  82--103 &  76-- 96 \\
%8 &    --$^2$    &    --    &    --    \\
\hline \hline
    \end{tabular}
%    \begin{tabular}{ p{0.45\textwidth} }
%Note: 
%1: The FD and FDStubR results on Network~8 is not found
%The numerical results are in bandwidth unit.
%    \end{tabular} 
}
  \end{center}
\end{table}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.45\textwidth]{fig6}
    \caption{Comparison of various path protection schemes for link failures in two-layer networks}
    \label{fig:FDLink}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.45\textwidth]{fig7}
    \caption{Comparison of various path protection schemes for node failures in two-layer networks}
    \label{fig:FDNode}
  \end{center}
\end{figure}


\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig8}
%    \includegraphics[width=0.8\columnwidth]{net1}
    \caption{Net 1 ($N=6,L=9,N^b=10,L^b=22$)}
    \label{fig:net1}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig9}
%    \includegraphics[width=0.8\columnwidth]{net2}
    \caption{Net 2 ($N=7,L=12,N^b=12,L^b=25$)}
    \label{fig:net2}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig10}
%    \includegraphics[width=0.8\columnwidth]{net3}
    \caption{Net 3 ($N=8,L=14,N^b=13,L^b=23$)}
    \label{fig:net3}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig11}
%    \includegraphics[width=0.8\columnwidth]{net4}
    \caption{Net 4 ($N=10,L=16,N^b=17,L^b=31$)}
    \label{fig:net4}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.43\textwidth]{fig12}
%    \includegraphics[width=0.85\columnwidth]{net5}
    \caption{Net 5 ($N=10,L=18,N^b=18,L^b=27$)}
    \label{fig:net5}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.43\textwidth]{fig13}
%    \includegraphics[width=0.85\columnwidth]{net6}
    \caption{Net 6 ($N=10,L=22,N^b=23,L^b=33$)}
    \label{fig:net6}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig14}
%    \includegraphics[width=0.8\columnwidth]{net7}
    \caption{Net 7 ($N=8,L=13,N^b=26,L^b=30$)}
    \label{fig:net7}
  \end{center}
\end{figure}

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=0.4\textwidth]{fig15}
%    \includegraphics[width=0.8\columnwidth]{net8}
    \caption{Net 8 ($N=12,L=24,N^b=50,L^b=82$)}
    \label{fig:net8}
  \end{center}
\end{figure}

\end{document}
